package arithmetic;

import java.util.Random;

import org.junit.jupiter.api.Test;

import utils.ListNodeUtils.ListNode;


/**
 * 链表随机抽奖
 * @author jiangfeng on 2022/6/4
 */
public class RandomLink {



    ListNode head;
    Random r;
    public void Solution(ListNode head) {
        this.head = head;
        this.r = new Random();
    }


    // 核心要点， 不过有多少个元素，收取的概率都是相等的。    
    public int getRandom() {
        int count = 0;
        // 不要影响了 链表指针
        ListNode ln = head;
        int result = 0;
        while(ln!=null){
            // 抽一次， 1/2 抽两次 1/2 +
            //  nextInt从0开始的。
            count++;
            int value = r.nextInt(count)+1;

            if(value == count){
                result =  ln.val;
            }
            ln = ln.next;
        }
        return result;
    }
    
    

    @Test
    public void test(){
        Solution(genLink(new int[]{1,2,3}));


        System.out.println(getRandom());
        System.out.println(getRandom());
        System.out.println(getRandom());
        System.out.println(getRandom());
        System.out.println(getRandom());
        System.out.println(getRandom());
        
    }

    public  ListNode genLink(int[] a){
        ListNode head = new ListNode(a[0]);
        ListNode next = head;
        for (int i = 1; i < a.length; i++) {
            next.next =new ListNode(a[i]);
            next = next.next;
        }
        return head;
    }

}
